1. Field of Invention
The present invention relates to an information embedding halftone screen encoding system serviceable for printed media, and particularly, relates to a method for generating information embedding halftone screen code.
2. Description of Related Arts
In recent years, people in this field have been dedicating intensive enthusiasm to the research of digital watermarking theory about embedding computer information into printed images or image backgrounds. For example, Japanese patent 2003-209679 discloses the interpolation identifying technology of detecting falsified printed documents via digital watermarking. This information embedding method is achieved by representing “1” or “0” with information modules having different inclined angles, followed by classical Fourier Transform to calculate the spreading directions of the different information modules. A distinctive drawback of such method is low efficiency of information recording. Especially, when information embedded is mixed with the printed contents, some of the printed contents might go through the Fourier transform randomly as well, thus introducing many stochastic noises and affecting the recognition rate. In addition, a similar technology has been published in China (East China Jiao Tong University Gazette Vol. 21, No. 1, February, 2004). It is well-known that the information embedding technology would deteriorate the quality of original image.
Japanese patent (2004-007442) discloses another technology of identifying interpolations of recognized document information. This technology is achieved by converting the signature information or document information into individual small-size arrays to be utilized as digital watermark. Accordingly, the watermark images could be overprinted onto the target images for functional embedding purposes. On the other hand, images embedded with information, i.e. the integrated images could be segmented into a plurality of sub-images. By approximately calculating the correlation function values of the integrated image and the segmented images, the embedded information would be identified. However, since grey-scale of the target image to be embedded is not considered, the quality of the original image is inevitably damaged because of the overprinting procedure. Moreover, in order to enhance the robustness of anti-attack functions of the code, same information has been repetitively embedded into every basic array, thus significantly reducing the embedding efficiency. Furthermore, although the correlation coefficients are introduced in the encoding-detecting process, some important concepts, such as minimizing the maximum similarity value between codes, have been neglected.
Japanese patent (8-208196) “Code Printing Device and Code Printing Media Thereof” is the first case to disclose storing digital message onto paper. The main idea is to print defined dot code onto paper in hope of storing multimedia message, such as sound, onto paper. It is noted that such techniques are rather similar with two-dimensional bar, wherein a dot represents “1” and a blank represents “0” or vice versa. In reality, the encoding-detecting process of such method is difficult. This is due to the fact that under a high density dot matrix circumstance, the detecting process would be affected by misplacement of dots, distortion of target images, noise of the printing process, or paper defects. And more importantly, such method did not weigh a consideration of the characteristics of the halftone screen. Therefore, its aim is different from the aim of mixing information into printed contents as background or that of embedding a great deal of information into the related images.
The technology of embedding information into images is widely known because of the disclosure of Japanese patent (09-172537) and its U.S. Pat. No. (6,069,636) “Embedding information into images by varying pixel parameters”. This invention focuses on embedding message into target images or background images by representing the code “1” or “0” through varying pixel parameters like its shape, direction, or size. Additionally, different gray-scales could be selectively replaced by adjusting the pixel size. However, as a binary system, the embedding message could only be represented by “1” and “0”. And the maximum similarity would be too big between different codes. Also, the method merely embeds messages based on the tiny geometrical variances among pixel dots, without considering the differences of physical characteristic of the pixels. Finally, to detect the pixel dots employed for encoding message through tiny position displacement, reference pixel dots would have to be setup at two sides of the primary pixel dot. As a result, the information storage capacity would be reduced to below one third of original capacity.
Japanese patent (2002-234640) “Image Process Device and Process Method Thereof” discloses another method of embedding information into images. Aiming to embed binary sequence of “1” and “0” into target images to represent administrative information (copyright issue), the target images are segmented into many rectangles, each of which arrayed with 8*8 dot images, wherein each of the dot images is composed of 10*10 pixels. The different dot images are used to define “1” or “0” of the message. The same information would be repetitively generated in different rectangles. So the represented information of different rectangles would be the same. Afterwards, the rectangles containing dot images would be overprinted onto the original images to ultimately embed the encoded messages. It is noted that if the grayscale of the original image is larger than the grayscale of the dot image, the embedded information might be lost in application. On the other hand, if the grayscale of the original image is smaller than the grayscale of the dot image, it is likely that the quality of the original image would be reduced. Obviously, the information storing capacity would be very low since similar information is repeatedly embedded.
All the cases above are based on the traditional binary code. Here, it is worth pointing out that there is an unavoidable maximum similarity problem existing in the conventional binary code.
Equation 3 represents an example of a traditional binary code. Example (a) illustrates a method of generating a code. Example (b) illustrates the corresponding symbols with array relationship.
To obviate the pollution attack from paper, a 4-bit hexadecimal code could be repeatedly embedded for 4 times to generate a 16-bit hexadecimal code as shown in example (a). As shown in example (b), the code value is denoted by k, and the numbers next to k represent the numbers of code bits.
                                          (            a            )                    ⁢                                          ⁢                                                    0                                            1                                                                                                                          0                                            0                                                                                                                                                                                                                                                                                                                                                                                                                                                                0                                            1                                                                                                                          0                                            0                                                                    0                                            1                                                                                                                          0                                            0                                                                    0                                            1                                                                                                                          0                                            0                                                                    0                                            1                                                                                                                          0                                            0                                                    ⁢                                  ⁢                              (            b            )                    ⁢                                          ⁢                                                                      B                                      k                    ,                    D                                                                                                B                                      k                    ,                    1                                                                                                B                                      k                    ,                    2                                                                                                B                                      k                    ,                    3                                                                                                                        B                                      k                    ,                    4                                                                                                B                                      k                    ,                    5                                                                                                B                                      k                    ,                    6                                                                                                B                                      k                    ,                    7                                                                                                                        B                                      k                    ,                    B                                                                                                B                                      k                    ,                    9                                                                                                B                                      k                    ,                    10                                                                                                B                                      k                    ,                    11                                                                                                                        B                                      k                    ,                    12                                                                                                B                                      k                    ,                    13                                                                                                B                                      k                    ,                    14                                                                                                B                                      k                    ,                    15                                                                                                          [                  Equation          ⁢                                          ⁢          3                ]            
Equation 4 is an example of the code formation from equation 3.
                                                                                                              D                    0                                    ⁢                                      :                                                                              0                                            0                                            0                                            0                                                                                                                                                  0                                            0                                            0                                            0                                                                                                                                                  0                                            0                                            0                                            0                                                                                                                                                  0                                            0                                            0                                            0                                              ⁢                                          ⁢                                                                                          D                    8                                    ⁢                                      :                                                                              0                                            0                                            0                                            1                                                                                                                                                  0                                            0                                            0                                            1                                                                                                                                                  0                                            0                                            0                                            1                                                                                                                                                  0                                            0                                            0                                            1                                                    ⁢                                  ⁢                                                                                                  D                    1                                    ⁢                                      :                                                                              1                                            0                                            0                                            0                                                                                                                                                  1                                            0                                            0                                            0                                                                                                                                                  1                                            0                                            0                                            0                                                                                                                                                  1                                            0                                            0                                            0                                              ⁢                                          ⁢                                                                                          D                    9                                    ⁢                                      :                                                                              1                                            0                                            0                                            1                                                                                                                                                  1                                            0                                            0                                            1                                                                                                                                                  1                                            0                                            0                                            1                                                                                                                                                  1                                            0                                            0                                            1                                                    ⁢                                  ⁢                                                                                                  D                    2                                    ⁢                                      :                                                                              0                                            1                                            0                                            0                                                                                                                                                  0                                            1                                            0                                            0                                                                                                                                                  0                                            1                                            0                                            0                                                                                                                                                  0                                            1                                            0                                            0                                              ⁢                                          ⁢                                                                                          D                    A                                    ⁢                                      :                                                                              0                                            1                                            0                                            1                                                                                                                                                  0                                            1                                            0                                            1                                                                                                                                                  0                                            1                                            0                                            1                                                                                                                                                  0                                            1                                            0                                            1                                                    ⁢                                  ⁢                                                                                                  D                    3                                    ⁢                                      :                                                                              1                                            1                                            0                                            0                                                                                                                                                  1                                            1                                            0                                            0                                                                                                                                                  1                                            1                                            0                                            0                                                                                                                                                  1                                            1                                            0                                            0                                              ⁢                                          ⁢                                                                                          D                    B                                    ⁢                                      :                                                                              1                                            1                                            0                                            1                                                                                                                                                  1                                            1                                            0                                            1                                                                                                                                                  1                                            1                                            0                                            1                                                                                                                                                  1                                            1                                            0                                            1                                                    ⁢                                  ⁢                                                                                                  D                    4                                    ⁢                                      :                                                                              0                                            0                                            1                                            0                                                                                                                                                  0                                            0                                            1                                            0                                                                                                                                                  0                                            0                                            1                                            0                                                                                                                                                  0                                            0                                            1                                            0                                              ⁢                                          ⁢                                                                                          D                    C                                    ⁢                                      :                                                                              0                                            0                                            1                                            1                                                                                                                                                  0                                            0                                            1                                            1                                                                                                                                                  0                                            0                                            1                                            1                                                                                                                                                  0                                            0                                            1                                            1                                                    ⁢                                  ⁢                                                                                                  D                    5                                    ⁢                                      :                                                                              1                                            0                                            1                                            0                                                                                                                                                  1                                            0                                            1                                            0                                                                                                                                                  1                                            0                                            1                                            0                                                                                                                                                  1                                            0                                            1                                            0                                              ⁢                                          ⁢                                                                                          D                    D                                    ⁢                                      :                                                                              1                                            0                                            1                                            1                                                                                                                                                  1                                            0                                            1                                            1                                                                                                                                                  1                                            0                                            1                                            1                                                                                                                                                  1                                            0                                            1                                            1                                                    ⁢                                  ⁢                                                                                                  D                    6                                    ⁢                                      :                                                                              0                                            1                                            1                                            0                                                                                                                                                  0                                            1                                            1                                            0                                                                                                                                                  0                                            1                                            1                                            0                                                                                                                                                  0                                            1                                            1                                            0                                              ⁢                                          ⁢                                                                                          D                    E                                    ⁢                                      :                                                                              0                                            1                                            1                                            1                                                                                                                                                  0                                            1                                            1                                            1                                                                                                                                                  0                                            1                                            1                                            1                                                                                                                                                  0                                            1                                            1                                            1                                                    ⁢                                  ⁢                                                                                                  D                    7                                    ⁢                                      :                                                                              1                                            1                                            1                                            0                                                                                                                                                  1                                            1                                            1                                            0                                                                                                                                                  1                                            1                                            1                                            0                                                                                                                                                  1                                            1                                            1                                            0                                              ⁢                                          ⁢                                                                                          D                    F                                    ⁢                                      :                                                                              1                                            1                                            1                                            1                                                                                                                                                  1                                            1                                            1                                            1                                                                                                                                                  1                                            1                                            1                                            1                                                                                                                                                  1                                            1                                            1                                            1                                                                        [                  Equation          ⁢                                          ⁢          4                ]            
Dk is supposed to be a code, which is made up of the elements referred to as bit. In addition, the code's length is defined as the number of all the bits.
The code comprises 16 types expressed by 0-9 and A-F. For example, all the entries in code 0 (Do) are all 0. The entries for code 1 (D1) B1,0, B1,4, B1,8, B1,12 are 1, and then the rest are 0. The entries for code 2 (D2) B2,1, B2,5, B2,9, B2,13 are 1, and the rest are 0. The rest of the code (D3 to DF) follows the same construction as equation 4.
It is worth mentioning that, code 0 (D0) and code F (DF), code 1 (D1) and code E (DE), code 2 (D2) and code D (DD), code 3 (D3) and code C (DC), code 4 (D4) and code B (DB), code 5 (D5) and code A (DA), code 6 (D6) and code 9 (D9), code 7 (D7) and code 8 (D8) have their “0” and “1” in opposite position.
Furthermore, the similarity concept is introduced. If a code Sk comprises n digits Sk=(Bk,0, Bk,1, . . . BK,n−1), the sum of Logical nonequivalence of the corresponding Bk,i. can be calculated as equation 5. K is the code value, n is the symbol length, and m is the number of codes.
                                          B                          k              ⁢                                                          ⁢              i                                ⊕                                          ⁢                      B                          1              ,              j                                      =                  {                                                  ⁢                                                                                          0                      ⁢                                                                                          ⁢                                              (                                                                              B                                                          k                              ,                              i                                                                                =                                                      B                                                          1                              ,                              j                                                                                                      )                                                                                                                                                        1                      ⁢                                                                                          ⁢                                              (                                                                              B                                                          k                              ,                              i                                                                                ≠                                                      B                                                          1                              ,                              j                                                                                                      )                                                                                                        ⁢                                                          ⁢              i                        ,                          j              =              0                        ,            1            ,            2            ,            …            ,                          n              -              1                        ,                                                  ⁢            k            ,                          l              =              0                        ,            1            ,            2            ,            …            ,                          m              -              1.                                                          [                  Equation          ⁢                                          ⁢          5                ]                                          d          ⁡                      (                                          S                k                            ,                              S                l                                      )                          =                              ∑                          i              =                              0                ⁢                                                                    n              -              1                                ⁢                                          ⁢                                    (                                                B                                      k                    ⁢                                                                                  ⁢                    i                                                  ⊕                                  B                                      1                    ,                    j                                                              )                        ⁢                                                          [                  Equation          ⁢                                          ⁢          6                ]            
Equation 6 aggregates the results from equation 5, so that the distance between Sk and S1 can be calculated.dmin=mind(Sk, S1)  [Equation 7]
After their distance has been calculated, equation 7 takes out the minimum distance between Sk and S1.
                                          A            max                    =                                    n              -                              d                min                                      n                          ⁢                                                      [                  Equation          ⁢                                          ⁢          8                ]            
The maximum similarity value between Sk and S1 can be calculated by substituting results from equation 7 into equation 8.
The higher the similarity value between the codes, the harder it would be to detect the codes. On the other hand, the lower the similarity value between the codes, the easier it would be to detect the codes.
Equation 9 below shows an example of calculating the distance between codes.
                                                                                                                                                                                                                                                                                                             D                        2                                            ⁢                                              :                                                                                                  0                                                        1                                                        0                                                        0                                                                                                                                                                                          0                                                        1                                                        0                                                        0                                                                                                                                                                                          0                                                        1                                                        0                                                        0                                                                                                                                                                                          0                                                        1                                                        0                                                        0                                                                                                                                                                                                                                                                                                                                                      D                        3                                            ⁢                                              :                                                                                                  1                                                        1                                                        0                                                        0                                                                                                                                                                                          1                                                        1                                                        0                                                        0                                                                                                                                                                                          1                                                        1                                                        0                                                        0                                                                                                                                                                                          1                                                        1                                                        0                                                        0                                                                                                                          (                1                )                                                                                      B                                      2                    ,                    1                                                  ⁢                                                                  ⊕                                  B                                      3                    ,                    1                                                                                                                                                                                                                                      ⁢                      1                                                                            0                                                        0                                                        0                                                                                                                                                                                  ⁢                      1                                                                            0                                                        0                                                        0                                                                                                                                                                                  ⁢                      1                                                                            0                                                        0                                                        0                                                                                                                                                                                  ⁢                      1                                                                            0                                                        0                                                        0                                                                                                                          (                2                )                                                                                      d                  ⁢                                      (                                                                  D                        2                                            ,                                              D                        3                                                              )                                                  =                                                                            ∑                                              1                        =                        0                                            15                                        ⁢                                          (                                                                        B                                                      2                            ,                            1                                                                          ⊕                                                  B                                                      3                            ,                            1                                                                                              )                                                        =                  4                                                                                                                                                            [                  Equation          ⁢                                          ⁢          9                ]            
For example, the method of calculating the distance between code 2 (D2) and code 3 (D3) is showed below.
(1) Calculate the Logical nonequivalence between 2(D2) and 3(D3) according to equation 5.
(2) Sum the results from equation 5 to get the distance between 2(D2) and 3(D3). The distance in this case between 2(D2) and 3(D3) is 4.
Equation 10 clearly lists the distance between the codes in a determinant According to equation 8, it is calculated that the maximum similarity value is ¾.
                                                                                                                                               D                0                                                                    D                1                                                                    D                2                                                                    D                3                                                                    D                4                                                                    D                5                                                                    D                6                                                                    D                7                                                                    D                8                                                                    D                9                                                                    D                A                                                                    D                B                                                                    D                C                                                                    D                D                                                                    D                E                                                                    D                F                                                                                        D                0                                                                                                                        4                                      4                                      8                                      4                                      8                                      8                                      12                                      4                                      8                                      8                                      12                                      8                                      12                                      12                                      16                                                                          D                1                                                    4                                                                                                          8                                      4                                      8                                      4                                      12                                      8                                      8                                      4                                      12                                      8                                      12                                      8                                      16                                      12                                                                          D                2                                                    4                                      8                                                                                                          4                                      8                                      12                                      4                                      8                                      8                                      12                                      4                                      8                                      12                                      16                                      8                                      12                                                                          D                3                                                    8                                      4                                      4                                                                                                          12                                      8                                      8                                      4                                      12                                      8                                      8                                      4                                      16                                      12                                      12                                      8                                                                          D                4                                                    4                                      8                                      8                                      12                                                                                                          4                                      4                                      8                                      8                                      12                                      12                                      16                                      4                                      8                                      8                                      12                                                                          D                5                                                    8                                      4                                      12                                      8                                      4                                                                                                          8                                      4                                      12                                      8                                      16                                      12                                      8                                      4                                      12                                      8                                                                          D                6                                                    8                                      12                                      4                                      8                                      4                                      8                                                                                                          4                                      12                                      16                                      8                                      12                                      8                                      12                                      4                                      8                                                                          D                7                                                    12                                      8                                      8                                      4                                      8                                      4                                      4                                                                                                          16                                      12                                      12                                      8                                      12                                      8                                      8                                      4                                                                          D                8                                                    4                                      8                                      8                                      12                                      8                                      12                                      12                                      16                                                                                                          4                                      4                                      8                                      4                                      8                                      8                                      12                                                                          D                9                                                    8                                      4                                      12                                      8                                      12                                      8                                      16                                      12                                      4                                                                                                          8                                      4                                      8                                      4                                      12                                      8                                                                          D                A                                                    8                                      12                                      4                                      8                                      12                                      16                                      8                                      12                                      4                                      8                                                                                                          4                                      8                                      12                                      4                                      8                                                                          D                B                                                    12                                      8                                      8                                      4                                      16                                      12                                      12                                      8                                      8                                      4                                      4                                                                                                          12                                      8                                      8                                      4                                                                          D                C                                                    8                                      12                                      12                                      16                                      4                                      8                                      8                                      12                                      4                                      8                                      8                                      12                                                                                                          4                                      4                                      8                                                                          D                D                                                    12                                      8                                      16                                      12                                      8                                      4                                      12                                      8                                      8                                      4                                      12                                      8                                      4                                                                                                          8                                      4                                                                          D                E                                                    12                                      16                                      8                                      12                                      8                                      12                                      4                                      8                                      8                                      12                                      4                                      8                                      4                                      8                                                                                                          4                                                                          D                F                                                    16                                      12                                      12                                      8                                      12                                      8                                      8                                      4                                      12                                      8                                      8                                      4                                      8                                      4                                      4                                                                                                                                [                      Equation            ⁢                                                  ⁢            10                    ]                    
It is seen that conventional code neglected the issue of minimizing the maximum similarity value between codes. Therefore, it tends to make incorrect recognition if the printed media are subjected to fierce attacks such as pollution and disrepair.
Moreover, the traditional watermarking embedding method would lower the original image's quality after encoding.
Finally, the storing efficiency would be low according to conventional embedding process.